#include <iostream>
#include <sstream>
#include <fstream>
#include <iterator>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <deque>
#include <algorithm>
#include <sys/time.h>
//#include <sys/resource.h>
using namespace std;

typedef unsigned short int usitype;
typedef unsigned int uitype;
typedef short int sitype;
typedef vector<vector<sitype> > sivec;
typedef vector<vector<bool> > bvec;

struct pos{
    usitype row;
    usitype col;
};



class netInfo{
    public:
        usitype net,cell1,cell2,terminal1,terminal2,MD;
        netInfo(){
            net=0;cell1=0;cell2=0;terminal1=0;terminal2=0,MD=0;
        }
        void add(usitype n,usitype c1,usitype t1, usitype c2,usitype t2){
            net=n;
            cell1=c1;
            cell2=c2;
            terminal1=t1;
            terminal2=t2;

        }
        bool sortMD(netInfo &n1, netInfo &n2){
            return(n1.MD<n2.MD);
        }

};

//struct sortMD{
//    bool operator() (netInfo &n1, netInfo &n2){
//        return(n1.MD<n2.MD);
//    }
//};

typedef deque<pos> posq;

//Class contains the information of each cell: cell number, terminal number and net number
//Allows to keep track of the connections;

class cell{

    public:

        usitype cellID;
        usitype netNum[4];
        usitype cellPos[2];
        uitype cellCost;
        bool xMirror;
        bool yMirror;
        usitype col;

        cell *terminal[4];

        cell(){
            cellPos[0] =-1;
            cellPos[1]=-1;
            cellCost =0;
            cellID =0;
            terminal[0]=NULL;
            terminal[1]=NULL;
            terminal[2]=NULL;
            terminal[3]=NULL;
            netNum[0]=0;
            netNum[1]=0;
            netNum[2]=0;
            netNum[3]=0;
        }

 //set the cellID of the cell
        void setCellID(usitype c){
            cellID = c;
        }
//Get the cellID of the cell
        usitype getCellID(){
            return(cellID);
        }

        void setCellPos(usitype col, usitype row){
            cellPos[0]=col;
            cellPos[1]=row;
        }

//Add a new connection to the given terminal
        void addConnection(cell *ci, usitype n, usitype t ){
            netNum[t] = n;
            terminal[t]=ci;

        }

        void xMirrorToggle() {
		xMirror = !xMirror;
        }

        void yMirrorToggle() {
		yMirror = !yMirror;
        }

        usitype getTerminal(usitype n){
            for(usitype i=0;i<4;i++){
                if(netNum[i]==n){
                    return(i+1);
                }
            }
        }

        usitype getCellCost(usitype col,  usitype row){
            int xdist=0; int ydist=0; usitype cost=0;
            for(int i=0;i<4;i++){
                if(netNum[i]!=0){
                        xdist=abs(col-(terminal[i]->cellPos[0]));
                        ydist=abs(row-(terminal[i]->cellPos[1]));
                }
                cost=cost+xdist+ydist;
            }
            return(cost);
        }

        void updateCellCost(){
            cellCost = getCellCost(cellPos[0],cellPos[1]);
        }


};



class cellGrid{
    private:
        usitype rowrand1,colrand1,rowrand2,colrand2;
        usitype rowS,colS,rowT,colT;
        uitype initCost;
        pos source, target;
        posq posStack1,posStack2;
        sivec tmpGrid;
        bool tmpvals,tmpvalt;


    public:
        sivec grid,metal1,metal2;
        bvec freeGrid,expMetal1,expMetal2;
        vector<cell> cellList;
        vector<netInfo> netList;
        usitype gridLength;
        int totalCost;
        ofstream ff;

        cellGrid(char* fileName){
            usitype lineNum=0;
            usitype cNum, nNum;
            string line;
            ifstream inFile(fileName,ios_base::in);
            if(inFile.is_open()){
                while (inFile.good()) { 					//if file is good
                    if (lineNum == 0) {						//get the number of cells

                        getline (inFile,line);
                        cNum = atoi(line.c_str());
                        cellList.resize(cNum);

                        for(usitype i=0;i<cellList.size();i++){
                            cellList[i].setCellID(i+1);
                        }

                        gridLength = (usitype)sqrt((double)cNum);
                        double temp = sqrt((double)cNum);
                        if(gridLength != temp) {
                            gridLength++;
                        }
                        grid.resize(gridLength,vector<sitype>(gridLength,-1));
                        tmpGrid.resize(gridLength,vector<sitype>(gridLength,-1));//added
                        cout<<"gridlength: "<<gridLength<<endl;
                        lineNum++;
                        cout<<"Stage1:Successful:No of cells:"<<cNum<<" vect size"<<cellList.size()<<endl;
                    }

                    else if (lineNum == 1) {						//get the number of nets
                        getline(inFile,line);
                        nNum = atoi(line.c_str());
                        netList.resize(nNum);
                        lineNum++;
                        cout<<"stage2:Successful:No of Nets: "<<nNum<<" lineNum:"<<lineNum<<endl;
                    }

                    else if (lineNum == 2) {					//get the net connections
                        usitype tmp[5];
                        while (getline(inFile,line)){
                            istringstream iss(line,istringstream::in);
                            istream_iterator<int> it(iss);
                            istream_iterator<int> EOS;
                            int i=0;
                            for(;it!=EOS;it++){
                                tmp[i]=*it;
                                i++;
                            }

                                netList[tmp[0]-1].add(tmp[0]-1,cellList[tmp[1]-1].cellID,tmp[2]-1,cellList[tmp[3]-1].cellID,tmp[4]-1);
                                cellList[tmp[1]-1].addConnection(&cellList[tmp[3]-1],tmp[0],tmp[2]-1);
                                cellList[tmp[3]-1].addConnection(&cellList[tmp[1]-1],tmp[0],tmp[4]-1);

                        }
                        cout<<"Stage3: Successful"<<endl;
                    }
                }
                inFile.close();
            }
            else {
                cerr<<"Error: File \""<<fileName<<"\" cannot be opened.\nPlease check the file name that you have entered"<<endl;
            }

            ff.open("netl.txt");
            ///print cellList
            ff<<" size of cell list:"<<cellList.size()<<endl;
            for(int i=0;i<cellList.size();i++){
                ff<<cellList[i].cellID<<"\t";
                for(int j=0;j<4;j++){
                    if(cellList[i].netNum[j]!=0){
                        ff<<cellList[i].netNum[j]<<","<<j+1<<";"<<cellList[i].terminal[j]->getCellID()<<","<<cellList[i].terminal[j]->getTerminal(cellList[i].netNum[j])<<" ";
                    }
                }

                ff<<endl;
            }
            ff<<"Netlist:"<<endl;
            for(int i=0;i<netList.size();i++){
                ff<<netList[i].net<<" "<<netList[i].cell1<<" "<<netList[i].terminal1<<" "<<netList[i].cell2<<" "<<netList[i].terminal2<<endl;
            }
        }

        void createInitPlacement(){

            usitype rowIndex,colIndex;
            usitype n=0;
            vector<vector<usitype> >::iterator it;

            while(n<cellList.size()){
                rowIndex = rand()%gridLength;
                colIndex = rand()%gridLength;
                if(grid[rowIndex][colIndex] == -1){         //interchanging x and y for more randomness!
                    grid[rowIndex][colIndex] = n+1;
                    cellList[n].setCellPos(colIndex,rowIndex);
                    n++;
                }
            }
//Printing!!!!
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[i].size();j++){
                    cout<<grid[i][j]<<" ";
                }
                cout<<endl;
            }
            totalCost=getTotalCost();
            initCost=totalCost;

        }

        uitype getTotalCost(){
            uitype totalCost=0;
            for(int i=0;i<cellList.size();i++){
                cellList[i].cellCost=cellList[i].getCellCost(cellList[i].cellPos[0],cellList[i].cellPos[1]);
                totalCost+=cellList[i].cellCost;

            }
            //cout<<"Initial cost:"<<totalCost<<endl;
            return(totalCost);
        }

        void perterb(){

            rowrand1 = rand()%(gridLength);
            colrand1 = rand()%(gridLength);
            rowrand2 = rand()%(gridLength);
            colrand2 = rand()%(gridLength);
        }
        void updateTotalCost(){

            totalCost=totalCost+(getGain());
        }

        int getGain(){
            usitype newCost=0;
            usitype oldCost=0;
            int costdiff=0;
            if(grid[rowrand1][colrand1] >0){
                newCost=cellList[(grid[rowrand1][colrand1]-1)].getCellCost(colrand2,rowrand2);
                oldCost = cellList[grid[rowrand1][colrand1]-1].cellCost;
                //for(int i=0;i<4;i++){
                    //if(cellList[(grid[rowrand1][colrand1]-1)].netNum[i] != 0){
                           //newCost+=2*(abs(colrand1-colrand2)+abs(rowrand1-rowrand2));
                    //}
                //}
            }
            if(grid[rowrand2][colrand2] >0){
                newCost+=cellList[grid[rowrand2][colrand2]-1].getCellCost(colrand1,rowrand1);
                oldCost+= cellList[grid[rowrand2][colrand2]-1].cellCost;

            }


            costdiff = 2*(newCost-oldCost);
            return(costdiff);


        }

        double random(){
            return(rand()/((double)RAND_MAX + 1));
        }

        void accept(){
            updateTotalCost();
            if(grid[rowrand1][colrand1] >0){
                cellList[(grid[rowrand1][colrand1]-1)].setCellPos(colrand2,rowrand2);
                cellList[(grid[rowrand1][colrand1]-1)].updateCellCost();
            }
            if(grid[rowrand2][colrand2] >0){
                cellList[(grid[rowrand2][colrand2]-1)].setCellPos(colrand1,rowrand1);
                cellList[(grid[rowrand2][colrand2]-1)].updateCellCost();
            }
            int temp=grid[rowrand1][colrand1];
            grid[rowrand1][colrand1]=grid[rowrand2][colrand2];
            grid[rowrand2][colrand2]=temp;

        }

        void assignVec(sivec &tmpGrid,sivec &grid){
            for(int i=0;i<tmpGrid.size();i++){
                for(int j=0;j<tmpGrid[i].size();j++){
                    tmpGrid[i][j]=grid[i][j];
                }
            }
        }

        void Metropolis(double T, double M){
            uitype tmp,cost=initCost;
            while (M>0){
                perterb();

                double delH = (double)getGain();
                double randomProb = random();
                double con = exp((double)(-delH)/(T));
                if ((delH<0) || (randomProb < con)){
                    accept();
                    tmp=getTotalCost();
                    if(tmp<cost){
                        cost=tmp;
                        assignVec(tmpGrid,grid);
                    }
                }
                M=M-1;
            }
            cout<<"total cost:"<<cost;
            //cout<<"swap count"<<swapcout<<endl;
        }

        void SA(){
            double T=40, M=45, beta=2,maxTime=4000000, Time=0;//changed time
            //double T=40, M=45, beta=4,maxTime=4000000, Time=0;
            int n;
            while(Time<maxTime){
                    Metropolis(T,M);
                    Time=Time+M;
                    T=0.76*T;  //alpha
                    M=beta*M;
                    cout<<"T:"<<T<<endl;

            }

            int t=0;
            for(int i=0;i<cellList.size();i++){
                cellList[i].cellCost=cellList[i].getCellCost(cellList[i].cellPos[0],cellList[i].cellPos[1]);
                t+=cellList[i].cellCost;

            }
            cout<<"Actual t:"<<t<<endl;
//Printing!!!!
//            for(int i=0;i<grid.size();i++){
//                for(int j=0;j<grid[i].size();j++){
//                    ff<<grid[i][j]<<" ";
//                }
//                ff<<endl;
//            }
            ff.close();

        }

        void updateCellList(){
            assignVec(grid,tmpGrid);
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[i].size();j++){
                    if(grid[i][j]>0){
                        cellList[grid[i][j]-1].setCellPos(j,i);
                    }
                }
            }
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[i].size();j++){
                    cout<<grid[i][j]<<" ";
                }
                cout<<endl;
            }
        }
//////////////////////////////////////////ROUTING//////////////////////////////////////////////////////////////////


        usitype grid_length(){
            usitype a=6,b=4;
            //usitype length=gridLength*4+2;
            usitype length=gridLength*a+b;
            return(length);
        }

        void expandGrid(){
            usitype c=4;
            usitype length=grid_length();
            //usitype explength=(7+c*2)*gridLength+9;
            usitype explength=3*length;
            metal1.resize(length,vector<sitype>(length,-2));
            metal2.resize(length,vector<sitype>(length,-2));
            freeGrid.resize(length,vector<bool>(length,0));
            expMetal1.resize(explength,vector<bool>(explength,0));
            expMetal2.resize(explength,vector<bool>(explength,0));

        }

        void fillGrid(){
            usitype row,col,a=6,b=4;
            expandGrid();
            updateCellList();
            for(int i=0;i<grid.size();i++){
                for(int j=0;j<grid[i].size();j++){
                    if(grid[i][j]>0){
                        //row=4*i+2;col=4*j+2;
                        row=a*i+b;col=a*j+b;
                        metal1[row][col]=-1;//blocked!
                        metal2[row][col]=-1;



                        metal1[row+1][col]=-1;
                        metal2[row+1][col]=-1;


                        metal1[row][col+1]=-1;
                        metal2[row][col+1]=-1;


                        metal1[row+1][col+1]=-1;
                        metal2[row+1][col+1]=-1;

                    }

                }
            }
            usitype row1,col1,row2,col2;
//            for(int i=0;i<netList.size();i++){
//                 row1=a*cellList[netList[i].cell1-1].cellPos[1]+b;
//                 col1=a*cellList[netList[i].cell1-1].cellPos[0]+b;
//                 row2=a*cellList[netList[i].cell2-1].cellPos[1]+b;
//                 col2=a*cellList[netList[i].cell2-1].cellPos[0]+b;
//                if(netList[i].terminal1==0){
//                    metal1[row1-1][col1]=-4;
//                    metal2[row1-1][col1]=-4;
//                }
//                else if(netList[i].terminal1==1){
//                    metal1[row1-1][col1+1]=-4;
//                    metal2[row1-1][col1+1]=-4;
//                }
//                else if(netList[i].terminal1==2){
//                    metal1[row1+2][col1]=-4;
//                    metal2[row1+2][col1]=-4;
//                }
//                else if(netList[i].terminal1==3){
//                    metal1[row1+2][col1+1]=-4;
//                    metal2[row1+2][col1+1]=-4;
//                }
//
//                if(netList[i].terminal2==0){
//                    metal1[row2-1][col2]=-4;
//                    metal2[row2-1][col2]=-4;
//                }
//                else if(netList[i].terminal1==1){
//                    metal1[row2-1][col2+1]=-4;
//                    metal2[row2-1][col2+1]=-4;
//                }
//                else if(netList[i].terminal1==2){
//                    metal1[row2+2][col2]=-4;
//                    metal2[row2+2][col2]=-4;
//                }
//                else if(netList[i].terminal1==3){
//                    metal1[row2+2][col2+1]=-4;
//                    metal2[row2+2][col2+1]=-4;
//                }
//
//
//            }
        }

        void initFG(bvec &freeGrid){
            for(int i=0;i<freeGrid.size();i++){
                for(int j=0;j<freeGrid[i].size();j++){
                    freeGrid[i][j]=0;
                   if((metal1[i][j]==-1 || metal1[i][j]<-2 ) && (metal2[i][j]==-1 || metal2[i][j]<-2 ) ){
                        freeGrid[i][j]=1;
                   }
                }
            }
        }

        bool findSource(usitype i,usitype j,sivec &metal1, sivec &metal2, bvec &freeGrid){
            usitype a=6,b=4;
            cout<<" cellS:"<<cellList[i].cellID<<" "<<cellList[i].cellPos[1]<<" "<<cellList[i].cellPos[0];
            initFG(freeGrid);
                if(j==0) {
                    source.row=(a*cellList[i].cellPos[1]+b)-1;
                    source.col=(a*cellList[i].cellPos[0]+b);
                    if(metal1[source.row][source.col]!=-1){
                        metal1[source.row][source.col]=0;
                    }
                    if(metal2[source.row][source.col]!=-1){
                        metal2[source.row][source.col]=0;
                    }

                }
                else if(j==1) {
                    source.row= (a*cellList[i].cellPos[1]+b)-1;
                    source.col=(a*cellList[i].cellPos[0]+b)+1;
                    if(metal1[source.row][source.col]!=-1){
                        metal1[source.row][source.col]=0;
                    }
                    if(metal2[source.row][source.col]!=-1){
                        metal2[source.row][source.col]=0;
                    }

                }
                else if(j==2) {
                    source.row=(a*cellList[i].cellPos[1]+b)+2;
                    source.col=(a*cellList[i].cellPos[0]+b);
                    if(metal1[source.row][source.col]!=-1){
                        metal1[source.row][source.col]=0;
                    }
                    if(metal2[source.row][source.col]!=-1){
                        metal2[source.row][source.col]=0;
                    }

                }
                else if(j==3) {
                    source.row=(a*cellList[i].cellPos[1]+b)+2;
                    source.col=(a*cellList[i].cellPos[0]+b)+1;
                    if(metal1[source.row][source.col]!=-1){
                        metal1[source.row][source.col]=0;
                    }
                    if(metal2[source.row][source.col]!=-1){
                        metal2[source.row][source.col]=0;
                    }

                }
                return(true);
        }

            bool findTarget(usitype i,usitype k,sivec &metal1, sivec &metal2, bvec &freeGrid){
                usitype a=6,b=4;
                        cout<<" cellT:"<<cellList[i].cellID<<" "<<cellList[i].cellPos[1]<<" "<<cellList[i].cellPos[0]<<endl;
                        if(k==0) {
                            target.row=(a*cellList[i].cellPos[1]+b)-1;
                            target.col=(a*cellList[i].cellPos[0]+b);
                            if(metal1[target.row][target.col]!=-1){
                                metal1[target.row][target.col]=-3;
                            }
                            if(metal2[target.row][target.col]!=-1){
                                metal2[target.row][target.col]=-3;
                            }

                        }
                        else if(k==1) {
                            target.row=(a*cellList[i].cellPos[1]+b)-1;
                            target.col=(a*cellList[i].cellPos[0]+b)+1;
                            if(metal1[target.row][target.col]!=-1){
                                metal1[target.row][target.col]=-3;
                            }
                            if(metal2[target.row][target.col]!=-1){
                                metal2[target.row][target.col]=-3;
                            }

                        }
                        else if(k==2) {
                            target.row=(a*cellList[i].cellPos[1]+b)+2;
                            target.col=(a*cellList[i].cellPos[0]+b);
                            if(metal1[target.row][target.col]!=-1){
                                metal1[target.row][target.col]=-3;
                            }
                            if(metal2[target.row][target.col]!=-1){
                                metal2[target.row][target.col]=-3;
                            }

                        }
                        else if(k==3) {
                            target.row=(a*cellList[i].cellPos[1]+b)+2;
                            target.col=(a*cellList[i].cellPos[0]+b)+1;
                            if(metal1[target.row][target.col]!=-1){
                                metal1[target.row][target.col]=-3;
                            }
                            if(metal2[target.row][target.col]!=-1){
                                metal2[target.row][target.col]=-3;
                            }

                        }

            return(true);
        }

        bool validateST(sivec &metal1,sivec &metal2,pos source,pos target){

            if(metal1[source.row][source.col]==-1 && metal2[source.row][source.col]==-1){
                return(false);
            }
            else if(metal1[target.row][target.col]==-1 && metal2[target.row][target.col]==-1){
                return(false);
            }
            else {
                //cout<<"Validated"<<endl;
                return(true);
            }
        }

        bool label(pos source,pos target,sivec &metal1, sivec &metal2, bvec &freeGrid, posq &posStack){
            bool found = false,end=false;
            bool top_flag= false, bot_flag =false, right_flag=false, left_flag=false;
            usitype length=grid_length();
            deque<usitype> val;
            usitype row,col,value;
            pos tmp;
            val.push_back(0);
            posStack.push_front(source);
            cout<<"tarf.row:"<<target.row<<" tor.col:"<<target.col<<endl;
            //initFG(freeGrid);
            freeGrid[source.row][source.col]=1;

            //if(metal1[source.row][source.col]!=-1){
                //cout<<"posStack:"<<posStack.size()<<endl;
                //cout<<"source:"<<metal[source.row][source.col]<<endl;
                //while(!found && posStack.size()!=0){
                while(!end){
                //cout<<"found:"<<found<<endl;
                //cout<<"cond"<<(!top_flag & !bot_flag & !left_flag & !right_flag)<<endl;
                    tmp=posStack.back();
                    posStack.pop_back();
                    //value=val.back();
                    //val.pop_back();
                    row=tmp.row; col=tmp.col;
                     cout<<posStack.size()<<endl;

                    if((top_flag & bot_flag & left_flag & right_flag)){
                        end=true;
                        //return(found);
                    }

                        if((row+1 < length) && (freeGrid[row+1][col]==0)){
                            //cout<<" bot1";
                            if(row+1==target.row && col==target.col){
                                found=true;
                            }
                            else{
                                freeGrid[row+1][col]=1;
                                if(metal1[row+1][col]==-2){
                                    metal1[row+1][col]=val.back()+1;
                                }
                                if(metal2[row+1][col]==-2){
                                    metal2[row+1][col]=val.back()+1;
                                }
                                tmp.row=row+1;tmp.col=col;value=val.back()+1;
                                posStack.push_front(tmp);
                                val.push_front(value);
                                if(row==length-2){bot_flag=true;}
                            }
                        }
                        if((row-1 > -1) && (freeGrid[row-1][col]==0)){
                            //cout<<" top1";
                            if(row-1==target.row && col==target.col){
                                found=true;
                            }
                            else {
                                freeGrid[row-1][col]=1;
                                if(metal1[row-1][col]==-2 ){
                                    metal1[row-1][col]= val.back()+1;
                                }
                                if(metal2[row-1][col]==-2 ){
                                    metal2[row-1][col]= val.back()+1;
                                }
                                tmp.row=row-1;tmp.col=col;value=val.back()+1;
                                posStack.push_front(tmp);
                                val.push_front(value);
                                if(row==1){top_flag=true;}
                            }
                        }
                        if((col-1 > -1) && (freeGrid[row][col-1]==0)){
                            //cout<<" left1";
                            if(row==target.row && col-1==target.col){
                                found=true;
                            }
                            else {
                                freeGrid[row][col-1]=1;
                                if(metal1[row][col-1]==-2 ){
                                    metal1[row][col-1]= val.back()+1;
                                }
                                if(metal2[row][col-1]==-2 ){
                                    metal2[row][col-1]= val.back()+1;
                                }
                                tmp.row=row;tmp.col=col-1;value=val.back()+1;
                                posStack.push_front(tmp);
                                val.push_front(value);
                                if(col==1){left_flag=true;}
                            }
                        }
                        if((col+1 < length) && (freeGrid[row][col+1]==0)){
                            //cout<<" right1"<<endl;
                            if(row==target.row && col+1==target.col){
                                found=true;
                            }
                            else {
                                freeGrid[row][col+1]=1;
                                if(metal1[row][col+1]==-2){
                                    metal1[row][col+1]= val.back()+1;
                                }
                                if(metal2[row][col+1]==-2){
                                    metal2[row][col+1]= val.back()+1;
                                }
                                tmp.row=row;tmp.col=col+1;value=val.back()+1;
                                posStack.push_front(tmp);
                                val.push_front(value);
                                if(col==length-2){right_flag=true;}
                            }
                        }
                        val.pop_back();
                    //}
                }
                posStack.clear();
                val.clear();
                cout<<"label over"<<endl;
                //cout<<"val size:"<<val.capacity()<<endl;
            return(found);
        }

        void retracePath(pos source, pos target, sivec &metal1, sivec &metal2, int v){

            usitype dist;
            usitype row=target.row, col=target.col,exprow,expcol;
            usitype length=grid_length();
            sitype tmp[4]={-4,-4,-4,-4};
            if(metal1[row][col]==-3){
                if(row+1<row+1 < length) { tmp[0]=metal1[row+1][col];}
                if(row-1 > -1){ tmp[1]=metal1[row-1][col];}
            }
            if(metal2[row][col]==-3){
                if(col-1>-1){ tmp[2]=metal2[row][col-1];}
                if(col+1 < length){tmp[3]=metal2[row][col+1];}
            }
            int index=max_element(tmp,tmp+4)-tmp;
            usitype me=*max_element(tmp,tmp+4);
            dist=me+1;

            if(me>=0){
            if((index==2 || index==3)){
//                sitype tmp[4]={0,0,0,0};
//                if(row+1<row+1 < length) { tmp[0]=metal1[row+1][col];}
//                if(row-1 > -1){ tmp[1]=metal1[row-1][col];}
//                if(col-1>-1){ tmp[2]=metal1[row][col-1];}
//                if(col+1 < length){tmp[3]=metal1[row][col+1];}

//                dist=*max_element(tmp,tmp+4)+1;
                //cout<<" dist:"<<dist<<endl;
                cout<<"enter m1"<<endl;
                cout<<"row:"<<row<<" col:"<<col<<endl;
                metal1[row][col]=v;

                //if()
                //expMetal1[row][col]
                while(row!=source.row || col!=source.col){
                    dist--;

//                    else if(row+1 < length && metal1[row+1][col]==dist){
//                        row=row+1;
//                    }
//                    else if(row-1 > -1 && metal1[row-1][col]==dist){
//                        row=row-1;
//                    }
                    if(dist==0){
                        row=source.row;
                        col=source.col;
                    }
                    else if(col-1>-1 && metal1[row][col-1]==dist){
                        cout<<" left";
                        col=col-1;
                    }
                    else if(col+1 < length && metal1[row][col+1]==dist){
                        col=col+1;
                        cout<<" right";
                    }
                    else if(metal2[row][col]==dist+1){
                        dist=dist+1;
                        metal2[row][col]=v;
                        while(row!=source.row || col!=source.col){
                            dist--;
                            if(dist==0){
                                row=source.row;
                                col=source.col;
                            }
                            else if(row+1 < length && metal2[row+1][col]==dist){
                                row=row+1;
                            }
                            else if(row-1 > -1 && metal2[row-1][col]==dist){
                                row=row-1;
                            }
//                            else if(col-1>-1 && metal2[row][col-1]==dist){
//                                col=col-1;
//                            }
//                            else if(col+1 < length && metal2[row][col+1]==dist){
//                                col=col+1;
//                            }

                            else if(metal1[row][col]==dist+1){
                                dist=dist+1;
                                break;
                            }
                            metal2[row][col]=v;
                        }
                        if(row==source.row && col==source.col)
                        {return;}
                    }

                    metal1[row][col]=v;
                }
            }
            else if((index==0 || index ==1)){
                //sitype tmp[]={metal2[row+1][col],metal2[row-1][col],metal2[row][col+1],metal2[row][col-1]};
                //cout<<"yes!"<<endl;
//                sitype tmp[4]={0,0,0,0};
//                if(row+1<row+1 < length) { tmp[0]=metal2[row+1][col];}
//                if(row-1 > -1){ tmp[1]=metal2[row-1][col];}
//                if(col-1>-1){ tmp[2]=metal2[row][col-1];}
//                if(col+1 < length){tmp[3]=metal2[row][col+1];}
//                dist=*max_element(tmp,tmp+4)+1;
                //cout<<" dist:"<<dist<<endl;
                cout<<"enter m2"<<endl;
                cout<<"row:"<<row<<" col:"<<col<<endl;
                metal2[row][col]=v;
                while(row!=source.row || col!=source.col){
                    dist--;

                    if(dist==0){
                        row=source.row;
                        col=source.col;
                    }
                    else if(row+1 < length && metal2[row+1][col]==dist){
                        row=row+1;
                    }
                    else if(row-1 > -1 && metal2[row-1][col]==dist){
                        row=row-1;
                    }
//                    else if(col-1>-1 && metal2[row][col-1]==dist){
//                        col=col-1;
//                    }
//                    else if(col+1 < length && metal2[row][col+1]==dist){
//                        col=col+1;
//                    }
                    else if(metal1[row][col]==dist+1){
                        //cout<<"dist in m1:"<<dist;
                        dist=dist+1;
                        metal1[row][col]=v;
                        while(row!=source.row || col!=source.col){
                            dist--;
                            if (dist==0){
                                row=source.row;
                                col=source.col;
                            }
//                            else if(row+1 < length && metal1[row+1][col]==dist){
//                                row=row+1;
//                            }
//                            else if(row-1 > -1 && metal1[row-1][col]==dist){
//                                row=row-1;
//                            }
                            else if(col-1>-1 && metal1[row][col-1]==dist){
                                col=col-1;
                            }
                            else if(col+1 < length && metal1[row][col+1]==dist){
                                col=col+1;
                            }

                            else if(metal2[row][col]==dist+1){
                                dist=dist+1;
                                break;
                            }
                            metal1[row][col]=v;
                        }
                        if(row==source.row && col==source.col)
                        {return;}
                    }
                    metal2[row][col]=v;
                }
            }
            }
        }

        void updateMetal(int j, pos source, pos target, sivec &metal1, sivec &metal2, bvec &expMetal1,bvec &expMetal2){
            if(j==0){
                //exp
            }
        }



        void clearLabels(sivec &metal,pos source, pos target){
            for(int i=0;i<metal.size();i++){
                for(int j=0;j<metal[i].size();j++){
                    if(metal[i][j]>0){
                        metal[i][j]=-2;
                    }
                }
            }
            if(metal[source.row][source.col]==0){
                metal[source.row][source.col]=-2;
            }
            if(metal[target.row][target.col]==-3){
                metal[target.row][target.col]=-2;
            }

        }

        bool sortMD(netInfo &n1, netInfo &n2){
            return(n1.MD<n2.MD);
        }
        void LeeRoute(){
            ofstream f,mag;
            f.open("o.txt");
            mag.open("1.mag");
            bool path,valid=0;
            int v=-5;


            int count=0,invalid=0;
            mag<<"magic"<<endl;
            mag<< "tech scmos"<<endl;
            mag<< "timestamp "<<time(0)<<endl;

            //sort(netList.begin(),netList.end(),netList.sortMD);

            for(int i=0;i<netList.size();i++){
                        cout<<"net:"<<netList[i].net<<endl;
                        //cout<<" cell1:"
                        findSource(netList[i].cell1-1,netList[i].terminal1,metal1,metal2,freeGrid);
                        findTarget(netList[i].cell2-1,netList[i].terminal2,metal1,metal2,freeGrid);
                        f<<"FreeGrid:"<<endl;
                        for(int m=0;m<freeGrid.size();m++){
                            for(int n=0;n<freeGrid[m].size();n++){
                                f<<freeGrid[m][n]<<" ";
                            }
                            f<<endl;
                        }
                        //findST(i,j,metal2);
                        f<<"NET:"<<netList[i].net<<endl;
                        if(validateST(metal1,metal2,source,target)){
                            path=label(source,target,metal1,metal2,freeGrid,posStack1);
                            //cout<<"path:"<<path<<endl;
                            //Printing!!!!
                                f<<"Metal1_label:"<<endl;//" net:"<<cellList[i].netNum[j]<<endl;
                                for(int i=0;i<metal1.size();i++){
                                    for(int j=0;j<metal1[i].size();j++){
                                        f<<metal1[i][j]<<" ";
                                    }
                                    f<<endl;
                                }
                                f<<"Metal2_label"<<endl;//" net:"<<cellList[i].netNum[j]<<endl;
                                for(int i=0;i<metal2.size();i++){
                                    for(int j=0;j<metal2[i].size();j++){
                                        f<<metal2[i][j]<<" ";
                                    }
                                    f<<endl;
                                }
                            if(path){
                                v--;
                                cout<<"v:"<<v<<endl;
                                retracePath(source,target,metal1,metal2,v);
                                clearLabels(metal1,source,target);
                                clearLabels(metal2,source,target);
                                count++;

                                //Printing!!!!
                                f<<"Metal1_path:"<<endl;//" net:"<<cellList[i].netNum[j]<<endl;
                                for(int i=0;i<metal1.size();i++){
                                    for(int j=0;j<metal1[i].size();j++){
                                        f<<metal1[i][j]<<" ";
                                    }
                                    f<<endl;
                                }
                                f<<"Metal2_path:"<<endl;//" net:"<<cellList[i].netNum[j]<<endl;
                                for(int i=0;i<metal2.size();i++){
                                    for(int j=0;j<metal2[i].size();j++){
                                        f<<metal2[i][j]<<" ";
                                    }
                                    f<<endl;
                                }
                            }
                            else{
                                //cout<<"Net:"<<cellList[i].netNum[j]<<endl;
                            }
                        }
                        else{
                            cout<<"Invalid net:"<<netList[i].net<<endl;
                            invalid++;
                        }
                    }
                //}
            //}
//            for(int k=0;k<netList.size();k++){
//                cout<<" "<<netList[k].;
//            }
//            cout<<endl;
            cout<<"total netts:"<<netList.size()<<endl;
            cout<<"invalid:"<<invalid<<endl;
            cout<<"Routed:"<<count<<endl;
            cout<<"Not Routed due to obstacles:"<<netList.size()-invalid-count<<endl;
            //cout<<expMetal1.size()<<endl;
//            for(int i=0;i<expMetal1.size();i++){
//                //cout<<"in1: ";
//                for(int j=0;j<expMetal1[i].size();j++){
//                    //cout<<" in2";
//                    f<<expMetal1[i][j]<<" ";
//                }
//                f<<endl;
//            }


            for(int i = 0; i <cellList.size(); i++) {
                mag << "use cell  cell_" << cellList[i].cellID <<endl;
                mag << "timestamp " << time(0) <<endl;
                mag << "transform 1 0 " << 15*cellList[i].cellPos[1]+9 << " 0 1 " << 15*cellList[i].cellPos[0]+9+6 << "\n";
                mag << "box 1 0 5 6\n";
            }
            mag<<"<<end>>"<<endl;
        mag.close();
        f.close();
        }
};


/****************************FUNCTION TO CALCULATE THE CPU TIME***********************************/ //taken from online source
//double getcputime(void){
//
//    struct timeval tim;
//    struct rusage ru;
//
//    getrusage(RUSAGE_SELF, &ru);
//    tim=ru.ru_utime;
//    double t=(double)tim.tv_sec + (double)tim.tv_usec / 1000000.0;
//    tim=ru.ru_stime;
//    t+=(double)tim.tv_sec + (double)tim.tv_usec / 1000000.0;
//
//    return t;
//}


int main(int argc, char*argv[]){

    srand(3895);
    cellGrid cg("one.net");
    cg.createInitPlacement();
    cg.SA();
    cg.fillGrid();
    cg.LeeRoute();

//    double cputime = getcputime();         //get the cpu time for the program and print
//    cout<<"#cputime:"<<cputime<<"s"<<endl;

    //////////To get the memory usage of the program and print--taken from an online source
//    FILE *fp;
//    pid_t pid = getpid();
//    char command[255];
//    char memory[255];
//    sprintf(command,"pmap  %d | grep total | awk '{ print $2 }'", pid);
//    fp = popen(command, "r");
//    fgets(memory, 255, fp);
//    cout<<"#memory usage:"<<memory<<endl;

}
